#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>

#define MAXSIZE 100
typedef struct {
    int i,j;
    int pre;
} Box;
typedef struct {
    Box data[MAXSIZE];
    int front,rear;
} SqQueue;
SqQueue initSqQueue() {
    SqQueue *sqQueue;
    sqQueue = (SqQueue*)malloc(sizeof (SqQueue));
    sqQueue->front = sqQueue->rear = 0;
    return *sqQueue;
}
bool isFull(SqQueue *queue) {
    return ((queue->rear + 1)%MAXSIZE == queue->front);
}
bool add(SqQueue *queue,Box *box) {
    if(isFull(queue)) {
        return false;
    }
    queue->data[queue->rear] = *box;
    queue->rear = (queue->rear + 1)%MAXSIZE;
    return true;
}
bool isEmpty(SqQueue *queue) {
    return (queue->rear == queue->front);
}
bool delete(SqQueue *queue) {
    if(isEmpty(queue)) {
        return false;
    }
    queue->front = (queue->front + 1)%MAXSIZE;
    return true;
}
Box peek(SqQueue *queue) {
    return queue->data[queue->front];
}
bool getLabyrinth(SqQueue *queue,int arr[10][10]) {
    Box *box3,*box1,*box2,*box4;
    box3 = (Box*) malloc(sizeof (Box));
    box1 = (Box*) malloc(sizeof (Box));
    box2 = (Box*) malloc(sizeof (Box));
    box4 = (Box*) malloc(sizeof (Box));
    if(arr[(queue->data[queue->rear - 1]).i][(queue->data[queue->rear - 1]).j] == 9) {
        return true;
    }
     if(arr[peek(queue).i -1][peek(queue).j] == -1) {

         box1->i = peek(queue).i - 1;
         box1->j = peek(queue).j;
         box1->pre = queue->front;
         add(queue,box1);
         arr[peek(queue).i - 1][peek(queue).j] = 3;
     }
    if(arr[peek(queue).i ][peek(queue).j + 1] == -1) {

        box2->i = peek(queue).i;
        box2->j = peek(queue).j + 1;
        box2->pre = queue->front;
        add(queue,box2);
        arr[peek(queue).i - 1][peek(queue).j] = 3;
    }
    if(arr[peek(queue).i +1][peek(queue).j] == -1) {

        box3->i = peek(queue).i + 1;
        box3->j = peek(queue).j;
        box3->pre = queue->front;
        add(queue,box3);
        arr[peek(queue).i - 1][peek(queue).j] = 3;
    }
    if(arr[peek(queue).i ][peek(queue).j - 1] == -1) {

        box4->i = peek(queue).i ;
        box4->j = peek(queue).j -1;
        box4->pre = queue->front;
        add(queue,box4);
        arr[peek(queue).i - 1][peek(queue).j] = 3;
    }
    delete(queue);
    getLabyrinth(queue,arr);
}
int main() {
    int arr[10][10] = {
            {8,8,8,8,8,8,8,8,8,8},
            {8,6,-1,8,-1,-1,-1,8,-1,8},
            {8,-1,-1,8,-1,-1,-1,8,-1,8},
            {8,-1,-1,-1,-1,8,8,-1,-1,8},
            {8,-1,8,8,8,-1,-1,-1,-1,8},
            {8,-1,-1,-1,-1,-1,-1,-1,-1,8},
            {8,-1,8,-1,-1,-1,-1,8,-1,8},
            {8,-1,8,8,8,-1,8,8,-1,8},
            {8,8,-1,-1,-1,-1,-1,-1,9,8},
            {8,8,8,8,8,8,8,8,8,8},
    };
   SqQueue Q1;
   Box box;
   box.j = 1;
   box.i = 1;
   box.pre = -1;
   Q1 = initSqQueue();
   add(&Q1,&box);
   getLabyrinth(&Q1,arr);
    //printf("%d",arr[0][0]);
   //delete(&Q1);
    return 0;
}
